This is a phase II, multi-center study of IV Tirapazamine plus Cisplatin in patients with non-small cell lung cancer (NSCLC) to estimate the rate of objective tumor response to tirapazamine when administered intravenously in combination with cisplatin; to estimate time to disease progression; and to assess the safety of the combined treatment regimen in this population.